package 开始的剑指offer8月.面经常用算法题09开始的;
import java.util.*;
// https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=188&&tqId=38594&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class NC19子数组的最大累加和问题0908 {



    public class Solution {
        /**
         * max sum of the subarray
         * @param arr int整型一维数组 the array
         * @return int整型
         */
        public int maxsumofSubarray (int[] arr) {
            // write code here
            int length = arr.length;
            int[] dp = new int[length];
            //边界条件
            dp[0] = arr[0];
            int max = dp[0];
            for (int i = 1; i < length; i++) {
                //转移公式
                dp[i] = Math.max(dp[i - 1], 0) + arr[i];
                //记录最大值
                max = Math.max(max, dp[i]);
            }
            return max;
        }

//         public int maxsumofSubarray(int[] arr) {
//         int length = arr.length;
//         int cur = arr[0];
//         int max = cur;
//         for (int i = 1; i < length; i++) {
//             cur = Math.max(cur, 0) + arr[i];
//             //记录最大值
//             max = Math.max(max, cur);
//         }
//         return max;
//     }
    }
}
